1. Field of the Invention
The present invention relates to a method, system, and program for reordering a queue of input/output commands directed toward a storage medium in a manner that maximizes system throughput.
2. Description of the Related Art
A hard disk drive receives input/output (I/O) commands with respect to locations on the disk drive. The I/O commands may be received at a rate faster than they can be executed with respect to the disk drive storage medium. In such case, the I/O commands are queued. FIG. 1 illustrates the arrangement of a recording surface of a disk drive 2 divided into concentric circular "tracks" on the disk surface. If there are multiple disks, then the vertical alignment of the tracks, on the disks aligned in parallel, together comprise a cylinder. The outer cylinder is shown as reference 4. Each cylinder is further divided into user data sectors 6a-h and prerecorded servo sectors 8a-h. A logical block address ("LBA") is used to address a specific location within the disk stack and is mapped by the disk drive control electronics to a cylinder or track, head number indicating a particular head in a multi-disk system, and sector.
The positioning time or total access time for an individual command can be broken-up into sequential phases, referred to as seek time and latency time. Seek time is the timer period for the servo system to position the actuator from the current head and cylinder position to the new target head and cylinder position. The latency time represents the remaining time, after seek completes, to position the head over the target sector. A "rotational time" involves the time to rotate the sector from the source or current sector location to position the target sector under the transducer read/write head. The latency time is the combination of the seek time and rotational time required to position the read/write head over the sector location that is the subject of the I/O operation.
Thus, the total access time is determined by two time movement operations, the seek time for radial positioning and the rotational access time for circumferential positioning the head over the target sector. To insure that the read/write head is positioned over the target sector at the completion of the radial and rotational positioning operations, the seek time must always be less than the rotational time. Further details of how to calculate the seek and rotational times are described in U.S. Pat. No. 5,729,718, entitled "System for Determining Lead Time Latency as Function of Head Switch, Seek, and Rotational Latencies and Utilizing Embedded Disk Drive Controller for Command Queue Reordering," which patent is incorporated herein by reference in its entirety.
Queued I/O commands do not have to be executed in the order they are received. Thus, the queued I/O commands may be reordered to maximize throughput. One reordering method, termed "Shortest Seek Time First," or SSTF, reorders commands such that the command with the shortest seek time with respect to the command being executed is executed next. This reordering method only considers the time to move the head in a radial position between tracks. The problem with queueing methods that consider only the seek time or time to change the radial position is that they do not consider rotational delay to spin the disk to a different circumferential position.
Current rotational position ordering (RPO) methods reorder the queue to minimize the combination of seek time and rotational time, or optimize total throughput. U.S. Pat. Nos. 5,729,718 and 5,548,795, entitled "Method for Determining Command Execution Dependencies Within Command Queue Reordering Process," which patents are incorporated herein by reference in their entirety, describe an RPO method for queuing commands that considers both seek and rotational delay times. Each queued command includes a field to store the results in calculating the delay time with respect to a reference command, which is the command currently being executed at the head of the queue. This latency time is calculated for each queued command with respect to the command at the head of the queue, or n calculations in a queue of n I/O commands. The command having the shortest latency time is promoted to the position immediately following the head of the queue. This algorithm is then repeated and latency times are calculated with respect to the just promoted I/O command. Thus, with current RPO reordering techniques, calculations in the order of n.sup.2 are performed to reorder the entire queue.
One problem with current RPO reordering techniques is the processor overhead needed to reorder the entire queue. Queue reordering operations can have significant affects on performance as the processing of I/O commands is delayed until the queue is reordered. Increases in the track storage capacity and number of addressable locations on the tracks results in likewise increases in the number of I/O commands directed to the storage device. It would be desirable to increase the queue length to accommodate the increase in I/O traffic associated with larger track capacity. However, one limitation on increasing the queue length is the time needed to reorder the queue. As the number of queued requests increases, the time to reorder the queue increases with the power of two. This increase in queue length in turn requires a substantial increase in the processing overhead to reorder the queue. Thus, one limitation on expanding the queue size in disk drives is the substantial increase in processor overhead needed to sort the longer queues.
Thus, there is a need in the art for an improved methodology for reordering I/O queues to accommodate increases in track capacity and the corresponding increase in queue length.